package com.tgy.leetcode;

/**
 * @Author: tgy
 * @Date: 1/12/21 11:20 AM
 */
public class _148_排序链表_快速排序 {


    public ListNode sortList(ListNode head) {

        if (head == null || head.next == null) {

            return head;
        }
        ListNode dummyHead = new ListNode();
        dummyHead.next = head;
        return quick(dummyHead,null);
    }

    private ListNode quick(ListNode head, ListNode end) {

        // 取值范围 (head, end)
        if (head == end || head.next == end || head.next.next == end) {

            return head;
        }


        ListNode centerPre = centerNode(head.next, end);

        ListNode pivot = centerPre.next;
        ListNode node = null;
        if (pivot != end) {

            centerPre.next = centerPre.next.next;
            pivot.next = head.next;
            head.next = pivot;
        }else {

            pivot = head.next;
        }
        node = pivot;




        ListNode lessDummyHead = new ListNode();
        ListNode lessTail = lessDummyHead;

        while (node.next != end) {

            if (node.next.val < pivot.val) {

                lessTail.next = node.next;
                lessTail = node.next;
                node.next = node.next.next;
            }else {

                node = node.next;
            }
        }

        lessTail.next = pivot;
        // 这里传递最后排序好的head
        head.next = lessDummyHead.next;

        quick(head,pivot);
        quick(pivot,end);

        return head.next;
    }


    private ListNode centerNode(ListNode start, ListNode end) {

        ListNode slow = start;

        ListNode fast = start.next.next;

        while (fast != end) {

            slow = slow.next;
            fast = fast.next;
            if (fast != end) {
                fast = fast.next;
            }
        }

        return slow;
    }


    public static void main(String[] args) {


        ListNode root = ListNode.general(new int[]{4,19,14,5,-3,1,8,5,11,15});

        _148_排序链表_快速排序 sortList = new _148_排序链表_快速排序();

        ListNode sortRoot = sortList.sortList(root);

        System.out.println(sortRoot);
    }
}
